§1.1. Field of the Invention
The present invention concerns establishing a path, such as a label-switched path, through a network, where the path is subject to constraints. In particular, the present invention concerns the communication of constraint information in instances where a given node of the network cannot, or does not wish to, determine the entire path.
§1.2. Description of Related Art
The description of art in this section is not, and should not be interpreted to be, an admission that such art is prior art to the present invention.
Many large networks are made up of interconnected nodes (referred to as “routers” below without loss of generality). The routers may be geographically distributed throughout a region and connected by links (e.g., optical fiber, copper cable, wireless transmission channels, etc.). In such a network, each router typically interfaces with (e.g., terminates) multiple input links and multiple output links. Addressed data (referred to as “packets” below without loss of generality) traverse the network by being forwarded from router to router until they reach their destinations (as typically specified in by so-called layer-3 addresses in the packet headers). Unlike switches, which establish a connection for the duration of a “call” or “session” to send data received on a given input port out on a given output port, routers determine the destination addresses of received packets and, based on these destination addresses, determine, in each case, the appropriate output link on which to send them. Since, unlike switches, routers are not connection-based, packets having the same destination address may actually traverse different paths through the network.
In some cases, however, it may be deemed desirable to establish a fixed path through at least a part of the network for a group of packets, commonly referred to as a “flow”. More specifically, merely using known routing protocols (e.g., shortest path algorithms) to determine paths is becoming unacceptable in light of the ever-increasing volume of Internet traffic and the mission-critical nature of some Internet applications. Such known routing protocols can actually contribute to network congestion if they to not account for bandwidth availability and traffic characteristics when constructing routing (and forwarding) tables.
Traffic engineering permits network administrators to map traffic flows onto an existing physical topology. In this way, network administrators can move traffic flows away from congested shortest paths to a less congested path. One traffic engineering technique, in which a fixed path is established, is known as label switching. The fixed path will be from a front-end node (e.g., an ingress router) to a tail-end node (e.g., an egress router). The fixed path may be determined by the front-end node. Once a path is determined, each router in the path may be configured to forward packets to the next (“downstream”) router in the path. Routers in the path determine that a given set of packets (e.g., a flow) are to be sent over the fixed path (as opposed to being routed individually) based on unique labels added to the packets.
When the fixed path through the network is being determined, information about the nodes and links in the network may be considered. For example, the fixed path, or parts thereof, may be subject to constraints, and/or certain characteristics of the path may be minimized, or maximized. In some cases, however, the front-end node (or an intermediate node) will not have access to sufficient information to determine a path to the tail-end node, or a path to the tail-end node that satisfies the constraints. In such cases, the front-end node cannot, by itself, establish the fixed path to the tail-end node. Even if the front-end node has access to such information, it may nonetheless be desired to delegate some or all of the responsibility for computing the fixed path. In either case, if path determination is to be delegated to another facility (e.g., a downstream node), constraints, if any, should be communicated to that facility.